BZOJ 1088 扫雷Mine

Description

相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的,第一列里面某些格子是雷,而第二列没有雷,如下图: 由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Input

第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000)

Output

一个数,即第一列中雷的摆放方案数。

Sample Input

2
1 1

Sample Output

2

Solution

本来是抱着做水题的心态来的
第一眼以为是个DP,然后各种推,i位置被i-1,i,i+1三个位置限制真心恶心
根本推不下去,然后死在DP里了
最后偷偷看了一眼题解做这种题也要看题解我的心好痛
发现只要确定了第一个位置是否有雷,整个棋盘都被确定了
然后就好水好水……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>

#define maxn 10000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

bool flag;
int f[maxn],a[maxn];
int n,ans;

int main()
{

#ifndef ONLINE_JUDGE
freopen("1088.in","r",stdin);
freopen("1088.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int t=0;t<=a[1];t++){
f[1]=t,flag=true;
for(int i=2;i<=n;i++){
f[i]=a[i-1]-f[i-1]-f[i-2];
if( f[i]>=2 || f[i]<0 ){
flag=false;
break;
}
}
if( f[n-1]+f[n]!=a[n] ) flag=false;
if( flag ) ans++;
}
printf("%d",ans);
return 0;
}